/*
 * @lc app=leetcode.cn id=842 lang=java
 *
 * [842] 将数组拆分成斐波那契序列
 */

// @lc code=start
class Solution {
    /**
     * 回溯+剪支
     * 剪支应该就是指对不满足的情况下可以直接跳过后续回溯步骤
     * 
     * 三处可以进行剪枝操作。
     * 拆分出的数如果不是 0，则不能以 0 开头
     * 拆分出的数必须符合 32 位有符号整数类型
     * 如果列表中至少有2个数，并且拆分出的数已经大于最后2个数的和，就不需要继续尝试拆分了。
     */
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> list = new ArrayList<Integer>();
        backtrack(list, S, S.length(), 0, 0, 0);
        return list;
    }
	/**
     * 
     * @param list 结果放置位置
     * @param S 遍历的字符串
     * @param length S的长度，避免每次都计算S.length
     * @param index 当前指针位置，是用来截取数字的
     * @param sum   前两个数的和 , 为了比对 cur == sum 时 list.add
     * @param prev 记录前一个数的值，为了后面更新sum = prev + cur
     * @return bool值，false带表非结果，剪枝
     */
    public boolean backtrack(List<Integer> list, String S, int length, int index, int sum, int prev) {
        //边界条件判断，如果截取完了,返回list.size() >= 3的true或者false
        //如果是false这个组合的最后一个会被减去，进行下一个可能的组合尝试。
        if (index == length) {//index超出了范围，证明回溯完了。
            return list.size() >= 3;  
        }
        long currLong = 0;//存当前截取出来的数
        for (int i = index; i < length; i++) {
            if (i > index && S.charAt(index) == '0') {//i>index代表这个数不止一位，且第一位为0，显然不满足条件，可以剪枝。
                break;
            }
            currLong = currLong * 10 + S.charAt(i) - '0';//获得当前这个数，因为可能超过int，所以用long
            if (currLong > Integer.MAX_VALUE) {//大于int的最大值，可以剪枝
                break;
            }
            int curr = (int) currLong;//转成int
            if (list.size() >= 2) {//list中已有两个数
                if (curr < sum) {//小于前两个数的和，此时可能第三个数再加一位数是可能相等的，故继续
                    continue;//跳出循环进行下一个循环。
                } else if (curr > sum) {//第三个数大于前两个的和，剪枝
                    break;//结束这个循环
                }
            }
            list.add(curr);//只有list中大于两个数，且curr == sum 才会执行到这一句。
            if (backtrack(list, S, length, i + 1, prev + curr, curr)) {//递归执行
                //此时 index=i+1 ,新的 sum = pre+curr，新的pre == curr
                return true;
            } else {
                list.remove(list.size() - 1);//如果是false证明不满足，减去这个继续
            }
        }
        return false;
    }
}
// @lc code=end

